# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
#
#  示例 1：
# 输入：n = 3
# 输出：["((()))","(()())","(())()","()(())","()()()"]
#
#  示例 2：
# 输入：n = 1
# 输出：["()"]
from typing import List


class Solution:
    def __init__(self):
        self.cache = {0: ['']}

    """
    分治算法
    要保证分解后的问题是一个最小的不可拆分的问题（找到第一个不可划分的整体）。
    分：将原问题分解成两个子问题
        1. k - 1 个括号能生成的所有正确的括号字符串 A
        2. n- k 个括号能生成的所有正确的括号字符串  B
    合并：
        规则：(a)b
        之所以a 需要括号包裹，是因为要保证 a 是一个不可拆分的整体
    """

    def generateParenthesis2(self, n: int) -> List[str]:
        # 记忆化，避免重复计算
        if n in self.cache:
            return self.cache[n]
        if n == 0:
            return ['']
        res = []
        for k in range(1, n + 1):
            tmp_res1 = self.generateParenthesis2(k - 1)
            tmp_res2 = self.generateParenthesis2(n - k)
            for r1 in tmp_res1:
                for r2 in tmp_res2:
                    res.append(f'({r1}){r2}')
        self.cache[n] = res
        return res

    def generateParenthesis1(self, n: int) -> List[str]:
        res = []

        def backTrack(singleRes: str, leftNum: int, rightNum: int) -> None:
            if len(singleRes) == 2 * n:
                res.append(singleRes)
                return
            if leftNum > rightNum:  # 所剩可使用的左括号数比右括号数大，则不可能是有效括号(剪枝)
                return

            if leftNum > 0:
                backTrack(singleRes + '(', leftNum - 1, rightNum)
            if rightNum > 0:
                backTrack(singleRes + ')', leftNum, rightNum - 1)

        backTrack('', n, n)
        # print(len(res))
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        return self.generateParenthesis2(n)


if __name__ == "__main__":
    n = 3
    print(Solution().generateParenthesis(n))
